import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Description: LeetCode每日练习
 * @Author: zhanglinxin
 * @CreateTime: 2025-04-01
 * @Version: 1.0
 */
public class Solution202505 {
    /**
     * @Description: 给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri] 。
     * 每一个 queries[i] 表示对于 nums 的以下操作：
     * 将 nums 中下标在范围 [li, ri] 之间的每一个元素 最多 减少 1 。
     * 坐标范围内每一个元素减少的值相互 独立 。
     * 零数组 指的是一个数组里所有元素都等于 0 。
     * <p>
     * 请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。
     * 如果无法将 nums 变为一个 零数组 ，返回 -1 。
     * <p>
     * 示例 1：
     * 输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
     * 输出：1
     * 解释：
     * 删除 queries[2] 后，nums 仍然可以变为零数组。
     * 对于 queries[0] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
     * 对于 queries[1] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
     * <p>
     * 示例 2：
     * 输入：nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
     * 输出：2
     * 解释：
     * 可以删除 queries[2] 和 queries[3] 。
     * <p>
     * 示例 3：
     * 输入：nums = [1,2,3,4], queries = [[0,3]]
     * 输出：-1
     * 解释：
     * nums 无法通过 queries 变成零数组。
     * @param: [int[], int[][]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/5/22 14:13
     */
    public int maxRemoval(int[] nums, int[][] queries) {
        Arrays.sort(queries, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        int[] deltaArray = new int[nums.length + 1];
        int operations = 0;

        for (int i = 0, j = 0; i < nums.length; i++) {
            operations += deltaArray[i];
            while (j < queries.length && queries[j][0] == i) {
                heap.offer(queries[j][1]);
                j++;
            }
            while (operations < nums[i] && !heap.isEmpty() && heap.peek() >= i) {
                operations += 1;
                deltaArray[heap.poll() + 1] -= 1;
            }
            if (operations < nums[i]) {
                return -1;
            }
        }
        return heap.size();
    }

    public static void main(String[] args) {
        Solution202505 solution202504 = new Solution202505();
        int[] nums = {0, 0, 1, 1, 0, 0};
        int[][] queries = {{2, 3}, {0, 2}, {3, 5}};
        int i = solution202504.maxRemoval(nums, queries);
        System.out.println(i);
    }
}
